# 513.找树左下角的值
# 给定一个二叉树的根节点root，请找出该二叉树的最底层最左边节点的值。
# 假设二叉树中至少有一个节点。
#
# 示例1:
# 输入: root = [2, 1, 3]
# 输出: 1
#
# 示例2:
# 输入: [1, 2, 3, 4, null, 5, 6, null, null, 7]
# 输出: 7


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def findBottomLeftValue(self, root: [TreeNode]) -> int:
        # 好像层序遍历直接可以做啊，即最底层的第一个值，试试看，再递归吧
        from collections import deque
        que = deque()
        que.append(root)
        res = []
        while que:
            size = len(que)
            tmp = []
            for i in range(size):
                node = que.popleft()
                tmp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(tmp)
        result = res[-1][0]
        return result

    def findBottomLeftValue2(self, root: [TreeNode]) -> int:
        # 深度最大的叶子节点
        max_dep = 0
        res = 0
        # 1.确定参数和返回值
        def traver(root,depth):
            nonlocal max_dep,res # python的语法，函数内使用外部变量需要使用nonlocal
            # 2.确定终止条件 当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度
            if not root.left and not root.right:
                if depth > max_dep:
                    max_dep = depth
                    res = root.val
            if root.left:
                # 在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：
                depth += 1
                traver(root.left,depth)
                depth -= 1
            if root.right:
                depth += 1
                traver(root.right,depth)
                depth -= 1
        traver(root,0)
        return res


if __name__ == '__main__':
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(9)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.findBottomLeftValue2(a11)
    print(res)